package com.jjlin.chapter_2;

import java.util.*;
public class CD111{
    public static class Node{
        public int val;
        public Node next;
        public Node(int data){
            this.val = data;
        }
    }

    public static Node createNodeList(int[] nums){
        Node head = new Node(nums[0]);
        Node tmp = head;
        for(int i = 1; i < nums.length; i++){
            Node newNode = new Node(nums[i]);
            tmp.next = newNode;
            tmp = newNode;
        }
        return head;
    }

    //need n extra space
    public static boolean isPalindrome(Node head){
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        while(cur != null){
            stack.add(cur);
            cur = cur.next;
        }
        cur = head;
        while(!stack.isEmpty()){
            if(stack.pop().val != cur.val)
                return false;
            cur = cur.next;
        }
        return true;
    }

    //need n/2 extra space
    public static boolean isPalindrome1(Node head){
        if(head == null || head.next == null)
            return true;
        Node right = head;
        Node cur = head.next;//也可以这样写：Node cur = head
        //cur获取后半部分的结构
        while(right.next != null && right.next.next != null){
            right = right.next.next;
            cur = cur.next;
        }
        Stack<Node> stack = new Stack<>();
        while(cur != null){
            stack.add(cur);
            cur = cur.next;
        }
        cur = head;
        while(!stack.isEmpty()){
            if(stack.pop().val != cur.val)
                return false;
            cur = cur.next;
        }
        return true;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int len = sc.nextInt();
        int[] nums = new int[len];
        for(int i = 0; i < len; i++)
            nums[i] = sc.nextInt();
        Node head = createNodeList(nums);
//         System.out.println(isPalindrome(head));
        System.out.println(isPalindrome1(head));
    }
}
